#include "pathroutecalculate.h"

//https://www.cnblogs.com/smile233/p/8303673.html
PathRouteCalculate::PathRouteCalculate()
{

}


// 最短路径Dijkstra算法
void PathRouteCalculate::Dijkstra(Graph<string> G,int v)
{
    int dist[MaxSize];//  i到j的路径长度
    string path[MaxSize];// 路径的串
    int s[MaxSize];// 已找到最短路径的点的集合
    bool Final[MaxSize];//Final[w]=1表示求得顶点V0至Vw的最短路径
    // 初始化dist\path
    for (int i = 0; i < G.vertexNum; i++)
    {
        Final[i] = false;
        dist[i] = G.arc[v][i];
        if (dist[i] != MAXCOST)
            path[i] = G.vertex[v] + G.vertex[i];
        else
            path[i] = " ";
    }
    s[0] = v; // 初始化s
    Final[v] = true;
    int num = 1;
    while (num < G.vertexNum)
    {
        // 在dist中查找最小值元素
        int k = 0,min= MAXCOST;
        for (int i = 0; i < G.vertexNum; i++)
        {
            if (i == v)continue;
            if (!Final[i] && dist[i] < min)
            {
                k = i;
                min = dist[i];
            }
        }
        cout << dist[k]<<path[k]<<endl;
        s[num++] = k;// 将新生成的结点加入集合s
        Final[k] = true;
        // 修改dist和path数组
        for (int i = 0; i < G.vertexNum; i++)
        {
            if (!Final[i]&&dist[i] > dist[k] + G.arc[k][i])
            {
                dist[i] = dist[k] + G.arc[k][i];
                path[i] = path[k] + G.vertex[i];
            }
        }
    }
}

int dist[MaxSize][MaxSize];// 存放在迭代过程中求得的最短路径
string path[MaxSize][MaxSize];// vi到vj的最短路径
void PathRouteCalculate::Floyd(Graph<string> G)
{
    // 初始化
    for(int i=0;i<G.vertexNum;i++)
        for (int j = 0; j < G.vertexNum; j++)
        {
            if (i == j) { dist[i][j] = 0; path[i][j] = ""; }
            dist[i][j] = G.arc[i][j];
            if (dist[i][j] != MAXCOST)
                path[i][j] = G.vertex[i] + G.vertex[j];
            else
                path[i][j] = " ";
        }
    // 进行n次迭代
    for(int k=0;k<G.vertexNum;k++)
        for(int i=0;i<G.vertexNum;i++)
            for (int j = 0; j < G.vertexNum; j++)
                if (dist[i][k] + dist[k][j] < dist[i][j])
                {
                    dist[i][j] = dist[i][k] + dist[k][j];
                    path[i][j] = path[i][k] + path[k][j];
                }

    //显示结果
    for (int i = 0; i < G.vertexNum; i++)
      {
          for (int j = 0; j < G.vertexNum; j++)
          {
              if (i != j)
              {
                  cout << "顶点" << i << "到顶点" << j << "的最短路径长度为" << dist[i][j] << endl;
                  cout << "具体路径为:" << path[i][j] << endl;
              }
          }
      }
}
